package dkbta.ontology.elements.context;

import java.util.List;

import dkbta.ontology.Ontology;
import dkbta.ontology.Validatable;
import dkbta.ontology.elements.Element;
import dkbta.ontology.elements.ElementDef;
import dkbta.ontology.elements.ElementType;
import dkbta.ontology.loading.OntologyException;
import dkbta.ontology.values.ValueCondition;
import dkbta.processing.Patient;
import dkbta.util.time.ISODuration;
import dkbta.util.time.TimeInterval;

public class Induction implements Validatable{
	/** The value condition on an ontology element on which the induction is based */
	private final ValueCondition _condition;

	/**
	 * Whether the start gap is relative the beginning or ending of the instance of the
	 * element the constraint refers to
	 */
	private final boolean _startRelativeToStart;

	/**
	 * The time gap relatively to either the beginning or ending of the element instance
	 * will define the start time of the context's instance
	 */
	private final long _startGap;

	/**
	 * Whether the end gap is relative the beginning or ending of the instance of the
	 * element the constraint refers to
	 */
	private final boolean _endRelativeToStart;

	/**
	 * The time gap relatively to either the beginning or ending of the element instance
	 * will define the end time of the context's instance
	 */
	private long _endGap;

	/**
	 * Initializes a context induction
	 * 
	 * @param valueCondition The value condition on an ontology element on which the
	 *        induction is based
	 * @param startRelativeToStart Whether the start gap is relative the beginning or
	 *        ending of the instance of the element the constraint refers to
	 * @param startGap The time gap relatively to either the beginning or ending of the
	 *        element instance will define the start time of the context's instance
	 * @param endRelativeToStart Whether the end gap is relative the beginning or ending
	 *        of the instance of the element the constraint refers to
	 * @param endGap The time gap relatively to either the beginning or ending of the
	 *        element instance will define the end time of the context's instance
	 */
	public Induction(ValueCondition valueCondition, boolean startRelativeToStart,
		ISODuration startGap, boolean endRelativeToStart, ISODuration endGap){
		_condition = valueCondition;
		_startRelativeToStart = startRelativeToStart;
		_startGap = startGap.toMillis();
		_endRelativeToStart = endRelativeToStart;
		_endGap = endGap.toMillis();
	}

	@Override
	public String toString(){
		StringBuilder sb = new StringBuilder();
		sb.append("Start [");
		sb.append(_startRelativeToStart ? "Start" : "End");
		sb.append(",");
		sb.append(_startGap);
		sb.append("], End [");
		sb.append(_endRelativeToStart ? "Start" : "End");
		sb.append(",");
		sb.append(_endGap);
		sb.append("]\r\n\t\t");
		sb.append(_condition);
		return sb.toString();
	}

	@Override
	public void validate(Ontology ontology) throws OntologyException{
		_condition.validate(ontology);
	}

	/**
	 * Returns the ontology element on which the induction is based
	 * 
	 * @param ontology A reference to the ontology
	 * @return The ontology element on which the induction is based
	 */
	public ElementDef getRelatedElement(Ontology ontology){
		return ontology.getElement(_condition.getElementType(), _condition
				.getElementName());
	}

	/**
	 * Induces all of the possible contexts from the instances (stored in the patient) of
	 * the element this induction is based on.
	 * 
	 * @param p The patient
	 * @param contexts The list of contexts to which induced contexts will be added
	 * @param contextName The name of the context that this induction belongs to
	 */
	void computeContexts(Patient p, List<Context> contexts, String contextName){
		// Obtaining all of the instances of the related element
		String elementName = _condition.getElementName();
		ElementType elementType = _condition.getElementType();
		List<? extends Element> elements = p.getElements(elementType, elementName);

		// Checking for each element whether it can induce the context
		// according to the associated condition
		for (Element e : elements){
			if (_condition.checkCondition(e)){
				// The element can induce the context so we construct
				// the induced context's time interval according to the
				// gaps specified in the ontology
				TimeInterval tInterval = e.getTimeInterval();
				long eStartTime = tInterval.getStartTime();
				long eEndTime = tInterval.getEndTime();
				long cStartTime = _startGap
						+ ((_startRelativeToStart) ? eStartTime : eEndTime);
				long cEndTime = _endGap + ((_endRelativeToStart) ? eStartTime : eEndTime);
				TimeInterval cTI = new TimeInterval(cStartTime, cEndTime);

				// The induced context may intersect with previously created
				// contexts so we remove them and update the interval of the induced
				// context to include (union) the time intervals of the intersecting
				// contexts
				int insertionIndex = getInsertionIndex(contexts, cTI);
				Context newContext = new Context(contextName, cTI);

				// Adding the new context to the list, sorted by start/end time
				// (seeing as there are no intersections between instances, sorted
				// order by start time implies sorted order by end time)
				contexts.add(insertionIndex, newContext);
			}
		}
	}

	/**
	 * Removes from the list those elements who intersect with the new interval and
	 * updates the new interval to be their and its union. Returns the index at which to
	 * insert the updated interval into the list
	 * 
	 * @param list List of elements (who have time intervals)
	 * @param newInterval The new time interval
	 * @return The index at which to insert the new interval
	 */
	private static int getInsertionIndex(List<? extends Element> list,
		TimeInterval newInterval){
		int listSize = list.size();
		if (listSize == 0){
			return 0;
		}

		long startTime = newInterval.getStartTime();
		long endTime = newInterval.getEndTime();
		int start = binarySearch(list, new TimeComparator(startTime){
			@Override
			public long getTime(TimeInterval ti){
				return ti.getStartTime();
			}
		});
		int end = binarySearch(list, new TimeComparator(endTime){
			@Override
			public long getTime(TimeInterval ti){
				return ti.getEndTime();
			}
		});

		if (start < 0){
			// There was no interval with the exact start time
			start = -start - 1;
			if (end < 0){
				// There was no interval with the exact end time
				end = -end - 1;
				end = checkEnd(list, newInterval, listSize, endTime, end);
				start = checkStart(list, newInterval, startTime, start);
			}else{
				// The start time wasn't found but the end time was (so we increase end by
				// one to include the end interval)
				++end;
				start = checkStart(list, newInterval, startTime, start);
			}
		}else{
			if (end < 0){
				// There was no interval with the exact end time
				end = -end - 1;
				end = checkEnd(list, newInterval, listSize, endTime, end);
			}else{
				// Both the start and end times are in the list
				// so we remove the range of elements between start and end (inclusive)
				// and for that we need to increase end by 1
				++end;
			}
		}

		int insertionIndex = start;

		// DecimalFormat df = new DecimalFormat("00");
		// System.out.println(newInterval + "\t S=" + ((start < 0) ? "-1" :
		// df.format(start))
		// + ", E=" + ((end < 0) ? "-1" : df.format(end)) + ": " + list + " -- "
		// + list.size());

		list.subList(start, end).clear();
		return insertionIndex;
	}

	private static int checkEnd(List<? extends Element> list, TimeInterval newInterval,
		int listSize, long endTime, int end){
		if (end < listSize){
			// We check the interval after us
			TimeInterval after = list.get(end).getTimeInterval();
			if (endTime >= after.getStartTime()){
				// Our interval doesn't end before the after interval starts
				newInterval.setEndTime(after.getEndTime());
				++end;
			}
			// Else end = the-index-of-after and we'll remove it
		}
		// Else end == listSize and we'll remove everything from start until
		// the end of the list as needed
		return end;
	}

	private static int checkStart(List<? extends Element> list, TimeInterval newInterval,
		long startTime, int start){
		if (start > 0){
			// Checking the interval before us
			TimeInterval before = list.get(start - 1).getTimeInterval();
			if (before.getEndTime() >= startTime){
				// The interval before ends after we start, so we take its
				// start time and start removing from it
				newInterval.setStartTime(before.getStartTime());
				--start;
			}
			// Else start = the-index-of-after and we'll remove it because
			// out start time is lower
		}
		// Else we will remove everything from the start of the list until the
		// end interval
		return start;
	}

	private static int binarySearch(List<? extends Element> list, TimeComparator comp){
		int low = 0;
		int high = list.size() - 1;
		while (low <= high){
			int mid = (low + high) >>> 1;
			TimeInterval ti = list.get(mid).getTimeInterval();
			long cmp = comp.compare(ti);

			if (cmp < 0)
				low = mid + 1;
			else if (cmp > 0)
				high = mid - 1;
			else
				return mid; // key found
		}
		return -(low + 1); // key not found.
	}

	private static abstract class TimeComparator{
		protected final long _time;

		private TimeComparator(long time){
			_time = time;
		}

		public long compare(TimeInterval ti){
			return getTime(ti) - _time;
		}

		public abstract long getTime(TimeInterval ti);
	}

}
